import java.util.Iterator;

public class RandomQueue<Item> implements Iterable<Item>
{
	private Item[] array;
	private int n = 0;

	public RandomQueue()
	{
		array = (Item[]) new Object[1];
	}
	
	public boolean isEmpty() // is it empty?
	{ return (array[0] == null); }
	
	public int size() // return the number of elements
	{ return n; }
	
	public void enqueue(Item item) // add an item
	{
		if(n == array.length) resize(2*array.length);
		array[n++] = item;
	}
	
	public Item sample() // return (but do not remove) a random item
	{ return array[(int)Math.ceil(StdRandom.random() * n-1)]; }
	
	public Item dequeue() // remove and return a random item
	{
		int rndNum = 0;
		Item item = array[rndNum];
		if(n == 0)
		{
			array[rndNum] = null;
			return item;
		}
		rndNum = (int)Math.ceil(StdRandom.random() * n-1);
		item = array[rndNum];
		array[rndNum] = null;
		if(rndNum < n) rearrange(rndNum);
		if(--n > 0 && n == array.length/4) resize(array.length/2);
		return item;
	}
	
	public Iterator<Item> iterator() // return an iterator over the items in random order
	{		
		return new RandomIrretator();
	}
	
	private void rearrange(int num)
	{
		for(int i = num;i < array.length-1; i++)
			array[i] = array[i + 1];
		array[n] = null;
	}
	
	private void resize(int max)
	{
		Item[] temp = (Item[]) new Object[max];
		for(int i = 0; i < n; i++)	temp[i] = array[i];
		array = temp;
	}
	
	private class RandomIrretator implements Iterator<Item> // Hehe, "Irretator" xD
	{
		int m = n-1;
		int i = n;
		Item[] rndArray = array;
		public RandomIrretator()
		{
			while(m >= 0)
			{
				int num = (int)Math.ceil(StdRandom.random() * m);
				Item temp = rndArray[m];
				rndArray[m--] = rndArray[num];
				rndArray[num] = temp;
			}
		}
		
		public boolean	hasNext()	{ return i > 0;			}
		public Item		next()		{ return rndArray[--i];	}
		public void		remove()	{						}
	}
	
	public static void main(String args[])
  {
    // Build a queue containing the Integers 1,2,...,6:
    RandomQueue<Integer> Q= new RandomQueue<Integer>();
    for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!
 
    // Print 30 die rolls to standard output
    StdOut.print("Some die rolls: ");
    for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
    StdOut.println();

    // Let's be more serious: do they really behave like die rolls?
    int[] rolls= new int [10000];
    for (int i = 0; i < 10000; ++i)
      rolls[i] = Q.sample(); // autounboxing! Also cool!
    StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
    StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
		  StdStats.stddev(rolls));
    
    // Let's look at the iterator. First, we make a queue of colours:
    
    RandomQueue<String> C= new RandomQueue<String>();
    C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

    Iterator I= C.iterator();
    Iterator J= C.iterator();

    StdOut.print("Two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.print(I.next()+" ");
    
    StdOut.print("\nEntire second shuffle: ");
    while (J.hasNext()) StdOut.print(J.next()+" ");

    StdOut.print("\nRemaining two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.println(I.next());
  }

}
